use std::cell::RefCell;
use std::fmt;
use std::rc::Rc;

pub struct TreeNode<T: PartialEq + Copy + fmt::Display> {
    p: Option<Rc<RefCell<TreeNode<T>>>>,
    key: T,
    left: Option<Rc<RefCell<TreeNode<T>>>>,
    right: Option<Rc<RefCell<TreeNode<T>>>>,
}

impl<T: PartialEq + Copy + fmt::Display> fmt::Display for TreeNode<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{} --- ", self.key)
    }
}

impl<T: PartialEq + Copy + fmt::Display> TreeNode<T> {
    pub fn left_v(&self) -> Option<T> {
        if let Some(l) = self.left.as_ref() {
            return Some(l.as_ref().borrow().key);
        } else {
            return None;
        }
    }
    pub fn right_v(&self) -> Option<T> {
        if let Some(l) = self.right.as_ref() {
            return Some(l.as_ref().borrow().key);
        } else {
            return None;
        }
    }
    pub fn p_v(&self) -> Option<T> {
        if let Some(l) = self.p.as_ref() {
            return Some(l.as_ref().borrow().key);
        } else {
            return None;
        }
    }
}

impl<T: PartialEq + Copy + fmt::Display> TreeNode<T> {
    pub fn build(k: T) -> Self {
        TreeNode {
            p: None,
            key: k,
            left: None,
            right: None,
        }
    }
}

pub struct BinarySearchTree<T: PartialEq + Copy + fmt::Display> {
    root: Option<Rc<RefCell<TreeNode<T>>>>,
}
impl<T: PartialEq + Copy + fmt::Display> fmt::Display for BinarySearchTree<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut node_list: Vec<Option<Rc<RefCell<TreeNode<T>>>>> = Vec::new();
        let mut node_list_temp: Vec<Option<Rc<RefCell<TreeNode<T>>>>> = Vec::new();
        node_list.push(self.root.clone());
        while !node_list.is_empty() {
            node_list_temp.clear();
            for node in node_list.iter() {
                if let Some(l) = node {
                    let temp = l.as_ref().borrow();
                    print!("{}", temp);
                    node_list_temp.push(temp.left.clone());
                    node_list_temp.push(temp.right.clone());
                } else {
                    print!("Nul --- ");
                }
            }
            println!("|");
            node_list = node_list_temp.clone();
        }
        write!(f, "Over")
    }
}

impl<T: PartialEq + Copy + fmt::Display + PartialOrd> BinarySearchTree<T> {
    pub fn build() -> Self {
        BinarySearchTree { root: None }
    }

    pub fn tree_search(
        &self,
        x: Option<Rc<RefCell<TreeNode<T>>>>,
        k: T,
    ) -> Option<Rc<RefCell<TreeNode<T>>>> {
        if let Some(l) = x.as_ref() {
            let key = l.as_ref().borrow().key;
            if k == key {
                return x.clone();
            } else if k < key {
                return self.tree_search(l.as_ref().borrow().left.clone(), k);
            } else {
                return self.tree_search(l.as_ref().borrow().right.clone(), k);
            }
        } else {
            return x.clone();
        }
    }

    pub fn tree_search_iter(&self, k: T) -> Option<Rc<RefCell<TreeNode<T>>>> {
        let mut node = self.root.clone();
        while let Some(l) = node.clone() {
            let temp = l.as_ref().borrow();
            let key = temp.key;
            if k == key {
                break;
            } else if k < key {
                node = temp.left.clone();
            } else {
                node = temp.right.clone();
            }
        }
        node
    }

    pub fn tree_minimum(
        &self,
        x: Option<Rc<RefCell<TreeNode<T>>>>,
    ) -> Option<Rc<RefCell<TreeNode<T>>>> {
        let mut node = x.clone();
        let mut node_p = node.clone();
        while let Some(l) = node.clone() {
            let temp = l.as_ref().borrow();
            node_p = node.clone();
            node = temp.left.clone();
        }
        node_p
    }

    pub fn tree_maximum(
        &self,
        x: Option<Rc<RefCell<TreeNode<T>>>>,
    ) -> Option<Rc<RefCell<TreeNode<T>>>> {
        let mut node = x.clone();
        let mut node_p = node.clone();
        while let Some(l) = node.clone() {
            let temp = l.as_ref().borrow();
            node_p = node.clone();
            node = temp.right.clone();
        }
        node_p
    }

    pub fn tree_successor(&self, x: TreeNode<T>) -> Option<Rc<RefCell<TreeNode<T>>>> {
        if x.right.is_some() {
            return self.tree_minimum(x.right.clone());
        }
        let mut y = x.p.clone();
        let mut x = x.key;
        let mut x_com;
        while let Some(l) = y.clone() {
            let temp = l.as_ref().borrow();
            if let Some(m) = temp.right.clone() {
                x_com = m.as_ref().borrow().key;
                if x == x_com {
                    x = temp.key;
                    y = temp.p.clone();
                }
            } else {
                break;
            }
        }
        y
    }

    pub fn tree_predecessor(&self, x: TreeNode<T>) -> Option<Rc<RefCell<TreeNode<T>>>> {
        if x.left.is_some() {
            return self.tree_maximum(x.right.clone());
        }
        let mut y = x.p.clone();
        let mut x = x.key;
        let mut x_com;
        while let Some(l) = y.clone() {
            let temp = l.as_ref().borrow();
            if let Some(m) = temp.left.clone() {
                x_com = m.as_ref().borrow().key;
                if x == x_com {
                    x = temp.key;
                    y = temp.p.clone();
                }
            } else {
                break;
            }
        }
        y
    }

    pub fn tree_insert(&mut self, z: TreeNode<T>) {
        let mut z = z;
        let mut y = None;
        let mut x = self.root.clone();
        while let Some(l) = x.clone() {
            y = x.clone();
            let temp = l.as_ref().borrow();
            if z.key < temp.key {
                x = temp.left.clone();
            } else {
                x = temp.right.clone();
            }
        }
        z.p = y.clone();
        if let Some(l) = y.clone() {
            let mut temp = l.as_ref().borrow_mut();
            if z.key < temp.key {
                temp.left = Some(Rc::new(RefCell::new(z)));
            } else {
                temp.right = Some(Rc::new(RefCell::new(z)));
            }
        } else {
            self.root = Some(Rc::new(RefCell::new(z)));
        }
    }

    fn transplant(&mut self, u: Rc<RefCell<TreeNode<T>>>, v: Option<Rc<RefCell<TreeNode<T>>>>) {
        let temp = u.as_ref().borrow();
        if let Some(l) = temp.p.as_ref() {
            let mut l_ref = l.as_ref().borrow_mut();
            if let Some(k) = l_ref.left_v() {
                if k == temp.key {
                    l_ref.left = v.clone();
                }
            } else {
                l_ref.right = v.clone();
            }
        } else {
            self.root = v.clone();
        }
        if let Some(l) = v.clone() {
            let mut l_ref = l.as_ref().borrow_mut();
            l_ref.p = temp.p.clone();
        }
    }

    pub fn tree_delete(&mut self, z: Rc<RefCell<TreeNode<T>>>) {
        let z_ref = z.as_ref().borrow();
        if z_ref.left.is_none() {
            self.transplant(Rc::clone(&z), z_ref.right.clone());
        } else if z_ref.right.is_none() {
            self.transplant(Rc::clone(&z), z_ref.left.clone());
        } else {
            let temp = self.tree_minimum(z_ref.right.clone());
            if let Some(y) = temp.clone() {
                let y_ref = y.as_ref().borrow();
                println!("被删除节点的后继： {}", y_ref.key);
                if let Some(n) = y_ref.p_v() {
                    if n != z_ref.key {
                        self.transplant(Rc::clone(&y), y_ref.right.clone());
                    }
                }
            }
            self.transplant(Rc::clone(&z), temp.clone());
            if let Some(y) = temp.clone() {
                let mut y_ref = y.as_ref().borrow_mut();
                y_ref.left = z_ref.left.clone();
                y_ref.right = z_ref.right.clone();
            }
        }
    }
}

/* 测试代码
    let mut b = BinarySearchTree::<i32>::build();
    b.tree_insert(TreeNode::build(3));
    println!("{}", b);
    println!("***************************");
    b.tree_insert(TreeNode::build(34));
    b.tree_insert(TreeNode::build(6));
    b.tree_insert(TreeNode::build(56));
    b.tree_insert(TreeNode::build(23));
    b.tree_insert(TreeNode::build(78));
    b.tree_insert(TreeNode::build(35));
    b.tree_insert(TreeNode::build(1));
    println!("{}", b);
    println!("***************************");
    if let Some(l) = b.tree_search_iter(3) {
        b.tree_delete(l);
    }
    println!("{}", b);
*/
